#define ull unsigned long long
class Solution {
    vector<ull>f,p;
    unordered_map<ull,bool>mp;
    string ans="";
    int n;
public:
    bool check(int m,string &s)
    {
        ull has=0;
        mp.clear();
        for(int i=1; i <= n - m;++i)
        {
            has=f[i+m]-f[i-1]*p[m+1];            
            if(mp[has])
            {
                if(ans.size()<m+1)ans=s.substr(i-1,m+1);
                return 1;
            }   
            mp[has]=1; 
        }
        return 0;
    }
    string longestDupSubstring(string s) {
        n=s.size();
        f.resize(n+1,0);
        p.resize(n+1,0);
        p[0]=1;
        for(int i=1;i<=n;++i)
        {
            f[i]=f[i-1]*131+(s[i-1]-'a'+1);
            p[i]=p[i-1]*131;
        }

        int l=0,r=n,m;
        while(l<r)
        {
            m=l+r>>1;
            if(check(m,s))l=m+1;
            else r=m;
        }
        return ans;
    }
};